﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetcodeTest._100._20
{
    public class Leetcode11
    {
        public void Test()
        {
            try
            {
                MaxArea(new int[] { 1, 1 });
            }
            catch (Exception ex)
            { }
        }

        /*
         11. Container With Most Water

        Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container. 

         */
        /*
         没看懂英文，百度的中文意思 
         题意是有个高度数组，就相当于隔板的高度，求数组中任意两隔板间盛水的最大量。隔板间的距离与较低隔板的高度乘积即为盛水的容量。
            */

        public int MaxArea(int[] height)
        {
            //网上看见的算法，想了很久才想通。。表示自己真菜
            int maxResult = 0;
            int tempValue = 0;
            int left = 0, right = height.Length - 1;
            while (left < right)
            {
                tempValue = Math.Min(height[left], height[right]) * (right - left);
                maxResult = Math.Max(tempValue, maxResult);
                if(height[left]<height[right])
                {
                    left++;
                }
                else
                {
                    right--;
                }
            }
            return maxResult;
        }

        /// <summary>
        /// 该做法超时
        /// </summary>
        /// <param name="height"></param>
        /// <returns></returns>
        public int MaxArea2(int[] height)
        {
            int maxResult = 0;
            int tempValue = 0;
            int num1 = 0;
            int num2 = 0;
            for (int i = 0; i < height.Length; i++)
            {
                num1 = height[i];
                for (int j = i + 1; j < height.Length; j++)
                {
                    num2 = height[j];
                    tempValue = j - i;
                    if (num1 < num2)
                        tempValue = tempValue * num1;
                    else
                        tempValue = tempValue * num2;

                    if (tempValue > maxResult)
                    {
                        maxResult = tempValue;
                    }
                }
            }
            return maxResult;
        }
    }
}
